模拟赛题解/2025.9.11 模拟赛

T1-买宝珠（pearl）

题面

鲁国突然从齐的侧翼发动反击，早已被锁链连接的齐国战车这时无法灵活的转过来应敌。于是，齐军一击即溃，只能丢盔弃甲，仓皇而逃。

在逃跑过程中，鲍叔牙竟然弄丢了管仲代购的鲁国特产。

已知鲁国特产是由 $n-1$ 条丝带连接 $n$ 个宝珠构成的。即你可以将鲁国特产看成一棵树。

树的每条边上的颜色都是 $k$ 种颜色中的一种。如果树上的一条路径是彩色的，意味着这条路径上至少包含两种不同颜色的边。

鲍叔牙还记得 $m$ 条彩色路径的起点和终点。他现在想知道满足条件的树有多少可能？

由于答案可能很大，所以请将答案对 $10^9+7$ 取模。

$3\leq n\leq60,1\leq a_i,b_i,c_j,d_j\leq n,1\leq m\leq 15,2\leq k\leq 10^9$。

题解

考虑暴力枚举每个人的决策，同时维护在前 $i$ 轮决策下，当前的 $S$ 集合，如果 $S=\varnothing$，那么立刻返回 $0$。时间复杂度是 $O(nm)$ 的，因为每次决策都会把 $S$ 分成两个不交的集合，每个元素都只会向一侧递归，一共递归 $m$ 层。

考虑对于先手来说，每次进行决策，如果他选择集合大小更小的那一侧，那么每次操作集合大小减半，需要 $\log n$ 次操作就可以使答案为 $0$，那么当 $m>2\log n$ 的时候，答案不可能大于 $0$。同理答案不可能小于 $0$，因此答案一定是 $0$。

时间复杂度 $O(n\log n)$。

T2-玩游戏（game）

题面

小 X 和小 Y 是好朋友，有一天他们在玩游戏，规则是：

1. 小 X 先手，小 Y 后手，轮流进行操作，共有 $m$ 轮操作，有一个集合初始为 $S={a_1,a_2,\cdots,a_n}$。
2. 第 $i$ 轮操作有一个参数 $b_i$，当前轮的操作者有以下两个选择：保留 $S$ 中所有是 $b_i$ 倍数的数字，或者保留 $S$ 中所有不是 $b_i$ 倍数的数字。
3. 进行了 $m$ 轮操作后两人获得的权值是 $S$ 中的数字之和，$S$ 可以为空。

小 X 希望权值最小，小 Y 希望权值最大，假设他们足够聪明，那么游戏最终的权值是多少。 $1\leq n\leq2\times10^4,1\leq m\leq2\times10^5,-4\times10^{14}\leq a_i\leq4\times10^{14},1\leq b_i\leq4\times10^{14}$。

题解

考虑不合法的方案。

如果 $m\geq2$，这样算会重复计算多条路径同时不合法的方案，我们发现 $n\leq60,m\leq15$，于是可以直接暴力枚举容斥。

具体来说，就是枚举不合法路径的集合 $S$，对于每条路径，把它所有边合并到某一条边上（如果路径有相交，当然是合并成一条边了）。然后统计合并后的边数 $cnt$，当 $|S|$ 为偶数，让答案加上 $cnt$，当 $|S|$ 为奇数，让答案减去 $cnt$，枚举路径集合可以直接状态压缩，合并可以用并查集实现。

时间复杂度为 $O(nm2^m)$。

T3-游乐场（playground）

题面

有 $n$ 个人来游乐场玩水上飞人，第 $i$ 个人想玩至少 $a_i$ 次，每次水上飞人恰好有两个人游玩，并且为了防止无聊，两个人 $u,v$ 至多一块玩一次水上飞人。每个人有一个勇气值 $v_i$，如果他的勇气值大于等于所有和他一块玩过水上飞人的人，那么他会收获 $b_i$ 的快乐值；如果他的勇气值小于等于所有和他一块玩过水上飞人的人，那么他会收获 $c_i$ 的快乐值。但如果他的勇气值恰好等于所有和他一块玩过水上飞人的人（或者没有和任何人玩过水上飞人），他并不能获得 $b_i+c_i$ 的快乐值，而是只能获得 $\max(b_i,c_i)$ 的快乐值。并且如果他的勇气值既不同时大于等于也不同时小于等于所有和他一起玩过的人，他就会生气并把游乐场炸掉。除此以外，如果有人没玩够 $a_i$ 次水上飞人，或者有两个人 $u,v$ 一块玩了至少两次水上飞人，游乐场也会被炸掉。

作为游乐场的管理员，你要规划若干次水上飞人，使得游乐场不会被炸掉，并且所有人的快乐值之和最大，如果无解输出 $-1$。

$n\leq 400$，$0\leq a_i\leq n$，$1\leq v_i\leq n$，$0\leq b_i,c_i\leq 10^9$。

题解

我们可以把题意改写：给每个人钦定他是大还是小，然后再判断每个人是否合法。对于一个人 $p$，设勇气值小于他的人的个数为 $x_p$，其中选大的人的个数是 $r_p$；勇气值大于他的人的个数为 $y_p$，其中选小的人的个数是 $t_p$；勇气值等于他的人的个数是 $d_p$，判句是：若 $p$ 选大，则 $a_p\leq x_p+d_p-1-r_p$；若 $p$ 选小，则 $a_p\leq y_p+d_p-1-t_p$。

先处理勇气值互不相同的情况。考虑按勇气值从小到大考虑人，那么记录一下当前有多少个人选大以及前面选小的人限制后面最多选几个小就能判断然后转移了。具体来说设 $\text{dp}$ 状态 $f_{i,j,k}$ 表示考虑完前 $i$ 人，选了 $j$ 个大的，$i+1$ 及以后最多选 $k$ 个小的，那么转移为：

$$f_{i-1,j,k}+b_i\rightarrow f_{i,j+1,k}(a_i\leq i-1-j),f_{i-1,j,k}+c_i\rightarrow f_{i,j,\min{(k-1,n-i-a_i)}}$$

暴力做复杂度 $O(n^3)$。

如果有相同的，那就不能直接以某一个顺序依次转移每个人。考虑把勇气值相同的人一块考虑，那么状态 $f_{i,j,k}$ 改为表示考虑完 $v_p\leq i$ 的 ，选了 $j$ 个大的，$v_p>i$ 的 $p$ 中最多选 $k$ 个小的，对于每一组勇气值相同的人我们只用知道选了几个大以及选小的内部最紧的限制即可像之前一样转移，但暴力实现复杂度最劣 $O(n^4)$。考虑把第二种转移里的取 $\min$ 改成分类讨论，如果是 $n-p-a_p$ 则只需要知道 $f_{i-1,j,k}$ 的 $\max$；如果是 $k-l$（$l$ 为选的小的个数），考虑维护一个转移数组 $h_{i-1,j,k}$，即 $f_{i-1,j,k}+q\rightarrow f_{i,j,k-l}$ 的最大系数 ，不难发现原来的转移相当于让 $k$ 这一维上的一个前缀的系数对一个数取 $\max$。使用后缀优化即可做到 $O(n^3)$。

T4-子矩阵（matrix）

题面

你要维护一个 $n\times m$ 的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记作 $A_{i,j}$。行和列从 $1$ 开始标号。初始时这个 $n\times m$ 的矩阵是全为 $0$ 的 $01$ 矩形。

你需要支持 $q$ 个操作，每个操作都是将一个从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的矩形反转，矩形反转即将矩阵中的元素 $0$ 变 $1$ 或者 $1$ 变 $0$。

你需要在所有操作结束之后，对最后的矩形求出有多少个子矩形，子矩阵要求：非空且连续，第一列全为 $1$ 或者最后一列全为 $1$。

答案对 $998244353$ 取模。

$1\leq n,m,q\leq2\times10^5$，$1\leq x_1\leq x_2\leq n$，$1\leq y_1\leq y_2\leq m$。

题解

考虑从左往右扫，使用支持区间反转的数据结构（平衡树）维护珂朵莉树，中间 $tag$ 翻转，左右两边 $split$ 或者 $merge$。

考虑对于 $\text{ds}$ 中的维护的一个区间，自诞生之日起它可能当过 $0$ 也当过 $1$，然后记录—下它当过多少次 $1$ 记为 $a$，考虑它对答案的贡献。

因为我们要的是对于 $\frac{1}{2}n(n+1)$ 个区间，每个区间求出 $m$ 列中有多少列全为 $1$，容易发现上面的一个区间 $(i,j)$ 会对 $i\leq x\leq y\leq j$ 的 $(x,y)$ 都产生 $a$ 的贡献。考虑这个东西在被破开连续段之前贡献只有两种，即取反和不取反，通过颜色段均摊之后我们可以拆成 $O(n)$ 个这样的 $(i,j)$，求出每一个区间 $(i,j)$ 后扫描线 + 线段树维护即可。

复杂度 $O(n\log n)$。